home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Club Amiga de Montreal - CAM
/
CAM_CD_1.iso
/
files
/
445.lha
/
RoadRoute_v1.6
/
United States
/
RoadScan.c
< prev
next >
Wrap
C/C++ Source or Header
|
1990-12-06
|
20KB
|
604 lines
/* after years of fiddling..
'v1.1 August 90
'Jim Butterfield */
/* compile with lc -Lcd -v <filename> */
#include <proto/exec.h>
#include <proto/dos.h>
#include <stdio.h>
#define BUFFERLINE 50
#define INFOSIZE sizeof(struct FileInfoBlock)
#define TRAILLEN 60
/* File Support structures */
struct CityData {
char *CityName; /* full name w/state */
char *StateName; /* state/province only */
struct CityData *CityLink; /* init letter chain */
struct CityData *StateLink; /* init letter chain */
struct RouteData *RoadList; /* roads to/from city */
struct CityData *WorkList; /* temp job queue */
struct CityData *NextCity[2]; /* result links */
/* Mindist[0] doubles as CityDupe flag during file input */
unsigned short MinDist[2]; /* closest so far */
unsigned char StateDupe; /* one name per state */
unsigned char Colum; /* goes with RoadList */
};
struct RouteData {
struct CityData *CityNum[2]; /* cities each end */
unsigned short Dist[2]; /* distance, time */
char *Hiway; /* name of Highway */
struct RouteData *RLink[2]; /* link for each city */
unsigned char Colm[2]; /* goes with RLink */
};
struct RouteData *Route0, *Route9;
struct CityData *City0, *City9;
struct CityData *CharLink[0x20];
struct CityData *ChStLink[0x20];
struct CityData *CityLink[0x100]; /* The only 1.1 change! */
struct CityData *CountLink[5];
static char InBuff[BUFFERLINE];
static struct CityData *Trail[TRAILLEN][2];
unsigned short TrailPoint[2];
void TimeShow(unsigned short,char *);
int CityMatch(struct CityData *,char *);
unsigned short ParseCities(char *,long);
unsigned short ParseRoutes(char *,long);
struct CityData * AskCity();
unsigned short Navigate(struct CityData *,struct CityData *);
void main()
{
long fh, lok;
unsigned short NextCol, NewCol;
unsigned short AllocCount, errnum;
struct FileInfoBlock *fibb;
long CitySize, RouteSize;
char *CityBlox, *RouteBlox, *DataScan, *Active;
char *CityScan, *CityPoint, *RoutePoint;
struct CityData *From, *Dest;
struct RouteData *NextRoute, *NewRoute, *ScanRoute;
unsigned short Cities, Roads;
unsigned short CityPSize, RoutePSize;
unsigned char Ct0; /* general character work value */
unsigned short Count, Links;
static char ActCity[]="Cities";
static char ActRoad[]="Roads";
for (Ct0=0; Ct0 < 0x20; Ct0++) CharLink[Ct0]= 0;
for (Ct0=0; Ct0 < 0x20; Ct0++) ChStLink[Ct0]= 0;
for (Ct0=0; Ct0 < 5; Ct0++) CountLink[Ct0]= 0;
AllocCount=0;
errnum=2; /* no memory */
if ( (long) (fibb = (struct FileInfoBlock *) AllocMem(INFOSIZE,0L))
!= 0L)
{
AllocCount=1;
errnum=3; /* file problems */
fprintf(stderr,"RoadScan V1.1 .. Jim Butterfield\n");
fprintf(stderr," Release version: 1990 08 13\n");
Cities=0;
Active=ActCity;
if ( (lok = Lock("Cities",ACCESS_READ)) != 0L)
{
if ( (fh=Examine(lok,fibb)) !=0L)
{
CitySize=fibb->fib_Size;
if ( (long) (CityBlox = AllocMem(CitySize,0L)) != 0L)
{
AllocCount=2;
if ( (fh = Open("Cities",MODE_OLDFILE)) != 0L)
{
errnum=0;
Read(fh,CityBlox,CitySize);
Close(fh);
} /* City file opened */
} /* data alloc OK */
} /* examine OK */
UnLock(lok);
} /* lock OK */
} /* examine alloc OK */
if (errnum == 0)
{
for (DataScan=CityBlox;DataScan < CityBlox+CitySize;DataScan++)
if (*DataScan == 0x0A) Cities++;
CityPSize=Cities*sizeof(struct CityData);
if ( (long) (CityPoint = AllocMem(CityPSize,0L)) != 0L)
AllocCount=3;
else
errnum=2;
}
if (errnum ==0 )
{
errnum=3; /* file problems */
Active=ActRoad;
Roads=0;
if ( (lok = Lock("Roads",ACCESS_READ)) != 0L)
{
if ( (fh=Examine(lok,fibb)) !=0L)
{
RouteSize=fibb->fib_Size;
if ( (long) (RouteBlox = AllocMem(RouteSize,0L)) != 0L)
{
AllocCount=4;
if ( (fh = Open("Roads",MODE_OLDFILE)) != 0L)
{
errnum=0;
Read(fh,RouteBlox,RouteSize);
Close(fh);
} /* file opened */
} /* data alloc OK */
} /* examine OK */
UnLock(lok);
} /* lock OK */
}
if (errnum == 0)
{
for (DataScan=RouteBlox;DataScan < RouteBlox+RouteSize;DataScan++)
if (*DataScan == 0x0A) Roads++;
RoutePSize=Roads*sizeof(struct RouteData);
if ( (long) (RoutePoint = AllocMem(RoutePSize,0L)) != 0L)
AllocCount=5;
else
errnum=2;
}
if (errnum == 0)
{
Active=ActCity;
fprintf(stderr,">> %d Cities\n",Cities);
City0 = (struct CityData *) CityPoint;
errnum=ParseCities(CityBlox,CitySize);
}
if (errnum == 0)
{
Active=ActRoad;
fprintf(stderr,">> %d Roads\n",Roads);
Route0 = (struct RouteData *) RoutePoint;
errnum=ParseRoutes(RouteBlox,RouteSize);
}
switch (errnum)
{
case 0: /* no errors, do main job */
printf("Scanning Cities...\n\n");
From=City0;
while (From<City9)
{
CityScan=From->CityName;
while (*(++CityScan) != ',');
*CityScan=0;
Count=0;
NextRoute=From->RoadList;
NextCol=From->Colum;
while (NextRoute != 0)
{
Dest=NextRoute->CityNum[1-NextCol];
for (Links=0; Links<Count; Links++)
if (CityLink[Links]==Dest && From>Dest )
printf("DUPE: %s,%s TO %s\n",
Dest->CityName,Dest->StateName,From->CityName);
CityLink[Count]=Dest;
Count++;
NewRoute=NextRoute->RLink[NextCol];
NewCol=NextRoute->Colm[NextCol];
NextRoute=NewRoute;
NextCol=NewCol;
}
if ( Count<5 )
{
From->WorkList=CountLink[Count];
CountLink[Count]=From;
}
From++;
}
From = CountLink[0];
if ( From !=0 )
{
printf("Following Cities have NO Roads !?!...\n");
printf(">>> connect or eliminate them!\n");
while (From != 0)
{
printf(" %s\n",From->CityName);
From = From->WorkList;
}
}
for (Count=1; Count<=3; Count++)
{
From = CountLink[Count];
if ( From!=0 )
{
printf("Following Cities have %d Roads...\n",Count);
printf(">>> you could save space if they were not needed!\n");
while (From != 0)
{
printf(" %s,%s ",From->CityName,From->StateName);
Ct0='[';
NextRoute=From->RoadList;
NextCol=From->Colum;
while (NextRoute != 0)
{
Dest=NextRoute->CityNum[1-NextCol];
printf("%c%s",Ct0,Dest->CityName);
NewRoute=NextRoute->RLink[NextCol];
NewCol=NextRoute->Colm[NextCol];
NextRoute=NewRoute;
NextCol=NewCol;
Ct0='-';
} /* wend, connecting-city list loop */
printf("]\n");
From = From->WorkList;
} /* wend, next city for this count-list */
} /* endif count-list not empty */
} /* next count-list */
Ct0=0;
for (ScanRoute=Route0; ScanRoute<Route9; ScanRoute++)
{
TrailPoint[0]=0;
TrailPoint[1]=0;
From=ScanRoute->CityNum[0];
Dest=ScanRoute->CityNum[1];
if ( Navigate(From,Dest)>1 )
{
if (Ct0==0)
printf("... Following DIRECT routes are not shortest!\n");
Ct0=1;
printf("%s,%s->%s \n",
From->CityName,From->StateName,Dest->CityName);
}
} /* next Road to analyze */
break;
case 1: /* trouble in file data */
fprintf(stderr,"----> Correct data in file %s and try again.\n",Active);
break;
case 2: /* AllocMem refused */
fprintf(stderr,"----> Not enough memory to run RoadRoute.\n");
break;
case 3: /* real trouble with file */
fprintf(stderr,"----> Can't proceed due to unreadable file %s.\n",Active);
break;
default:
fprintf(stderr,"System error: %d\n",errnum);
} /* error switch area */
switch (AllocCount)
{
case 5: FreeMem(RoutePoint,RoutePSize);
case 4: FreeMem( (char *) RouteBlox,RouteSize);
case 3: FreeMem(CityPoint,CityPSize);
case 2: FreeMem( (char *) CityBlox,CitySize);
case 1: FreeMem( (char *) fibb,INFOSIZE);
} /* memory cleanup */
if (errnum != 0)
{
fprintf(stderr,"Press any key to quit\n");
gets(InBuff);
}
}
void TimeShow(Time, Buffer)
unsigned short Time;
char *Buffer;
{
unsigned short MinFlag, radix, digit, SuppressLimit, FillChar, Hours[2];
Hours[0]=Time/60;
Hours[1]=Time%60;
SuppressLimit=1;
FillChar=':';
radix=10000;
while (radix>Hours[0] && radix>SuppressLimit)
{
radix/=10;
*Buffer++ =' ';
}
for (MinFlag=0;MinFlag<2;MinFlag++)
{
while (radix>0)
{
digit=Hours[MinFlag]/radix;
Hours[MinFlag]%=radix;
*Buffer++ =digit+'0';
radix/=10;
} /* more digits */
*Buffer++ =FillChar;
FillChar=0;
SuppressLimit=10;
radix=10;
} /* next MinFlag */
}
int CityMatch(TabPoint,CityText)
struct CityData *TabPoint;
char *CityText;
{
/* Name must match exactly; state is optional */
int Match, StateMatch;
char TablChar, TextChar;
char *TableName;
TableName=TabPoint->CityName;
TablChar=*TableName++; if (TablChar > 'Z') TablChar-=0x20;
TextChar=*CityText++; if (TextChar > 'Z') TextChar-=0x20;
Match=1;
StateMatch=0;
while (Match == 1 && TextChar != ',')
{
if (TablChar != TextChar)
{
if (TablChar ==',' && TextChar =='/') StateMatch=1;
else Match=0;
}
TablChar=*TableName++; if (TablChar > 'Z') TablChar-=0x20;
TextChar=*CityText++; if (TextChar > 'Z') TextChar-=0x20;
}
if (Match==1)
{
if (TablChar != 0 && TablChar !=',') Match=0;
if (TabPoint->MinDist[0]==1 && StateMatch ==0) Match=0;
}
return (Match);
}
unsigned short ParseCities(CitiesBlock,CBlockSize)
char *CitiesBlock;
long CBlockSize;
{
struct CityData *CityStruct, *CityScan;
char *LineBegin, *EndLine, *NewName, *OldName;
unsigned short CityError;
unsigned char CityIndex,NewChar,OldChar;
unsigned char FoundFlag, StateFlag;
CityError=0;
CityStruct = City0;
LineBegin = CitiesBlock;
FoundFlag=0;
for (EndLine=CitiesBlock;EndLine < CitiesBlock+CBlockSize;EndLine++)
if (*EndLine == ',' || *EndLine == 0x0A)
{
if (*EndLine == ',')
{
FoundFlag=1;
CityStruct->CityName=LineBegin;
/* MinDist[0] used as temporary dupe CityName flag */
CityStruct->MinDist[0]=0; /* No City Duplicate Name */
CityIndex = *LineBegin & 0x1F; /* strip first char */
CityScan = CharLink[CityIndex];
while (CityScan != 0)
{
NewName=LineBegin;
OldName=CityScan->CityName;
NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
while (NewChar == OldChar && NewChar != ',')
{
NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
}
if (NewChar == OldChar) /* Dupe City Name */
{
CityStruct->MinDist[0]=1;
CityScan->MinDist[0]=1;
}
CityScan = CityScan->CityLink;
} /* chain search for input city name */
CityStruct->CityLink = CharLink[CityIndex];
CityStruct->RoadList = 0;
CharLink[CityIndex]=CityStruct;
LineBegin=EndLine+1;
} /* end of comma..City parsing */
else /* NewLine */
{
*EndLine=0;
if (FoundFlag ==0)
{
fprintf(stderr,"*FILE Cities: NO COMMA:\n%s\n",LineBegin);
CityError=1;
}
FoundFlag=0;
CityStruct->StateName=LineBegin;
CityStruct->StateDupe=1;
CityIndex = *LineBegin & 0x1F; /* strip first char */
CityScan = ChStLink[CityIndex];
StateFlag = 0;
while (CityScan != 0 && StateFlag == 0)
{
NewName=LineBegin;
OldName=CityScan->StateName;
NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
while (NewChar == OldChar && NewChar !=0 && OldChar !=0)
{
NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
}
if (NewChar == OldChar)
{
CityScan->StateDupe=0;
StateFlag=1;
}
CityScan = CityScan->StateLink;
} /* more states in chain */
CityStruct->StateLink = ChStLink[CityIndex];
ChStLink[CityIndex]=CityStruct;
CityStruct++;
LineBegin=EndLine+1;
} /* end of NewLine parsing */
}
City9=CityStruct;
return(CityError);
}
unsigned short ParseRoutes(DataBlock,BlockSize)
char *DataBlock;
long BlockSize;
{
struct RouteData *RouteStruct;
struct CityData *CityScan, *FoundCity;
unsigned short ErrorFlag, CityColm, CityFlag, CityValue, Multiplier;
unsigned char CtNameKey, Digit;
char *LineStart,*LineEnd,*FieldStart,*FieldEnd,*NumPtr;
ErrorFlag=0;
RouteStruct = Route0;
LineStart = DataBlock;
for (LineEnd=DataBlock;LineEnd < DataBlock+BlockSize;LineEnd++)
if (*LineEnd == 0x0A)
{
*LineEnd=0;
FieldStart=LineStart;
for (CityColm=0 ; ErrorFlag==0 && CityColm < 2 ; CityColm++)
{
for (FieldEnd=FieldStart ;
*FieldEnd !=',' && FieldEnd < LineEnd ; FieldEnd++);
if (*FieldEnd !=',')
{
fprintf(stderr,"*FILE Roads: MISSING FIELDS:\n%s\n",LineStart);
ErrorFlag=1;
} /* no comma! */
/* ***** search city name chain */
CtNameKey = *FieldStart & 0x1F; /* strip first char */
CityScan = CharLink[CtNameKey];
CityValue =0;
while (CityScan != 0 && CityValue ==0)
{
if (CityMatch(CityScan,FieldStart)==1)
{
CityValue=1;
FoundCity=CityScan;
}
CityScan = CityScan->CityLink;
} /* chain search for input city name */
if (CityValue ==0)
{
fprintf(stderr,"*FILE Roads: CITY NOT FOUND:\n%s\n",LineStart);
ErrorFlag=1;
}
RouteStruct->CityNum[CityColm]=FoundCity;
RouteStruct->RLink[CityColm]=FoundCity->RoadList;
RouteStruct->Colm[CityColm]=FoundCity->Colum;
FoundCity->RoadList=RouteStruct;
FoundCity->Colum=CityColm;
FieldStart=FieldEnd+1;
} /* two-city loop */
/* Now grab mileage, time, and Hiway */
for (CityColm=0 ; ErrorFlag==0 && CityColm < 2 ; CityColm++)
{
for (FieldEnd=FieldStart ;
*FieldEnd !=',' && FieldEnd < LineEnd ; FieldEnd++);
if (*FieldEnd !=',')
{
fprintf(stderr,"FILE Roads: MISSING FIELDS:\n%s????\n",LineStart);
ErrorFlag=1;
} /* no comma! */
CityValue=0 ; CityFlag=0;
Multiplier=10;
for (NumPtr=FieldStart ; CityFlag==0 && NumPtr < FieldEnd ;
NumPtr++)
{
Digit=*NumPtr;
if (Digit >='0' && Digit<='9')
{
CityValue=CityValue * Multiplier + Digit - '0';
Multiplier=10;
}
else if (Digit ==':') Multiplier = 6;
} /* Scan for colon */
RouteStruct->Dist[CityColm]=CityValue;
FieldStart=FieldEnd+1;
} /* Two value paramemters */
RouteStruct->Hiway=FieldStart;
RouteStruct++;
LineStart=LineEnd+1;
} /* end of routefile scan */
Route9 = RouteStruct;
return(ErrorFlag);
} /* if no error, table build */
#define MENUSIZE 30
unsigned short Navigate(struct CityData *Start,struct CityData *Finish)
{
unsigned short Column, Travel;
unsigned short NextCol, NewCol;
struct CityData *CityScan;
struct CityData *BLink, *SearchCity;
struct CityData *ELink, *FLink, *OtherCity;
struct RouteData *NextRoute, *NewRoute;
static unsigned short MiniVal;
static unsigned short ThisDist[2], LCount[2];
for (CityScan=City0; CityScan<City9; CityScan++)
{
CityScan->WorkList = 0;
for (Column=0; Column<2; Column++)
{
CityScan->MinDist[Column]=9999;
CityScan->NextCity[Column]=0;
}
}
ELink=Finish;
MiniVal=0;
for (Column=0; Column<2; Column++)
{
Finish->MinDist[Column]=0;
ThisDist[Column]=9999;
}
SearchCity=Finish;
while (SearchCity != 0)
{
for (Column=0; Column<2; Column++)
{
if (SearchCity->MinDist[Column] < Start->MinDist[Column])
{
/* if (Column==0)
* printf("Scanning map at range: %d\n",SearchCity->MinDist[0]); */
MiniVal=SearchCity->MinDist[Column];
NextRoute=SearchCity->RoadList;
NextCol=SearchCity->Colum;
while (NextRoute != 0)
{
OtherCity=NextRoute->CityNum[1-NextCol];
Travel=MiniVal+NextRoute->Dist[Column];
if (OtherCity->MinDist[Column] > Travel)
/* found a new shortest path */
{
OtherCity->MinDist[Column]=Travel;
OtherCity->NextCity[Column]=SearchCity;
if (OtherCity->WorkList == 0 && ELink!=OtherCity)
{
BLink=SearchCity;
FLink=SearchCity->WorkList;
while (FLink!=0 && Travel>FLink->MinDist[Column])
{
BLink=FLink;
FLink=BLink->WorkList;
}
BLink->WorkList=OtherCity;
OtherCity->WorkList=FLink;
if (FLink==0) ELink=OtherCity;
} /* build new Worklist */
} /* shorter total distance */
if (Travel < ThisDist[Column]) ThisDist[Column]=Travel;
NewRoute=NextRoute->RLink[NextCol];
NewCol=NextRoute->Colm[NextCol];
NextRoute=NewRoute;
NextCol=NewCol;
} /* Try another route from SearchCity */
} /* if Search City within target range */
} /* Next Column (Mileage/Time) */
BLink=SearchCity->WorkList;
SearchCity->WorkList=0;
SearchCity=BLink;
} /* if SearchCity not zero, go back */
for (Column=0; Column<2; Column++)
{
LCount[Column]=0;
SearchCity=Start;
FLink=SearchCity->NextCity[Column];
while (FLink != 0)
{
LCount[Column]+=1;
Trail[TrailPoint[Column]++][Column]=FLink;
SearchCity=FLink;
FLink=SearchCity->NextCity[Column];
} /* wend for next FLink */
} /* next Column */
MiniVal=LCount[0];
if (MiniVal<LCount[1]) MiniVal=LCount[1];
return(MiniVal);
}